1. Technical Field of the Invention
The present invention relates generally to optical routing of data packets, and more specifically to a fiber delay line (FDL) optical buffering and routing method and system in an optical routing network.
2. Discussion of the Related Art
One of the major trends in networking in late 1990""s has been a relentless growth in demand for bandwidth in both enterprise and service provider networks. Driving the need for more bandwidth is a combination of factors. More users are connecting as the commercial Internet offers a new online experience for consumers. Internet computing applications, including multi-tier distributed databases, interactive multimedia communication, and electronic commerce rely on the network and demand network resources. A new generation of high-speed Internet access is emerging to meet bandwidth demands and further amplify core bandwidth requirements.
At the same time, competitive pressures make it imperative that networking costs be reduced even as the demand for capacity and new services increases. Successful companies are constantly on the lookout for new technologies which can provide a competitive edge and increase their cost effectiveness.
Optical networking has emerged as a solution to the bandwidth crunch. In particular, one new optical technologyxe2x80x94Dense Wavelength Division Multiplexing (DWDM)xe2x80x94promises to increase the capacity and performance of existing fiber optic backbones. DWDM offers a capacity upgrade solution with greater scalability and lower cost than available alternatives.
Wavelength Division Multiplexing (WDM) is a technique for increasing the information-carrying capacity of optical fiber by transmitting multiple signals simultaneously at different wavelengths (or xe2x80x9ccolorsxe2x80x9d) on the same fiber. In effect, WDM converts a single fiber into multiple xe2x80x9cvirtual fibers,xe2x80x9d each driven independently at different wavelengths. Systems with more than a small number of channels (two or three) are considered Dense WDM (DWDM) systems. Nearly all DWDM systems operate across a range of wavelengths in the 1550 nm low-attenuation window.
A DWDM system generally includes optical transmitters (lasers), an optical multiplexer and demultiplexer, an optical amplifier and optical receivers. DWDM systems use high,resolution, or narrowband, lasers transmitting in the 1550 nm wavelength band.
The optical multiplexer combines the transmit signals at different wavelengths onto a single optical fiber, and the demultiplexer separates the combined signal into its component wavelengths at the receiver. Several technologies are currently used for optical multiplexing and demultiplexing, including thin-film dielectric filters and various types of optical gratings. Some multiplexers are constructed as completely passive devices, meaning they require no electrical input. Passive optical multiplexers behave essentially like very high precision prisms to combine and separate individual colors of the WDM signal. Like prisms, most passive optical devices are reciprocal devices, meaning they function in the same way when the direction of the light is reversed.
Typically the multiplexing and demultiplexing functions are provided by a single device, a WDM multiplexer/demultiplexer. Some multiplexers have the ability to transmit and receive on a single fiber, a capability known as bi-directional transmission.
The optical receiver is responsible for detecting the incoming lightwave signal and converting it to an appropriate electronic signal for processing by the receiving device. Optical receivers are very often wideband devices able to detect light over a relatively wide range of wavelengths from about 1280-1580 nm. This is the reason why some seemingly incompatible devices can actually inter-operate. For instance, directly connecting two otherwise incompatible network interfaces having different transmitter wavelengths is usually not a problem, even though one end may be transmitting at 1310 nm and the other at 1550 nm.
An amplifier is sometimes used to boost an optical signal to compensate for power loss, or attenuation, caused by propagation over long distances. Electronic regeneration of a WDM signal requires a separate regenerator for each wavelength on each fiber. A single optical amplifier, conversely, can simultaneously amplify all the wavelengths on one fiber.
An additional benefit of the optical amplifier is that as a strictly optical device, it is a protocol-and bit rate-independent device. In other words, an optical amplifier operates the same way regardless of the framing or bit rate of the optical signal. This allows a great deal of flexibility in that an optically amplified link can support any combination of protocols (e.g. ATM, SONET, Gigabit Ethernet, PPP) at any bit rate up to a maximum design limit.
Despite the great advances in capacity, flexibility and reliability provided to the internet by the advent of optical routing of data, congestion and data packet loss is still an ongoing problem. An analysis of Internet traffic reveals a fractal or self-similar nature, (i.e., the traffic exhibits variability in all time scales), thus the conclusion is that the internet traffic is far from well behaved and hence congestion and the dropping of data packets are unavoidable. The dropping of a data packet is often the result of blocking, which occurs when two competing packets arrive at an input of the node simultaneously and desire the same output.
Variable length packets produce additional problems, while they can be processed directly they require a routing and scheduling methodology to control buffer occupancy and do not presently provide optimal packet loss rates.
The router includes a scheduling mechanism, an optical switch matrix with control logic capable of executing a method or algorithm, employing optical buffers and a memory for retaining routing information and instructions. It should be noted that there is no random access optical memory at high speeds. Fiber delay line (FDL) optical buffers are used as optical memory in all optical routers. The optical switch matrix and FDL are the building blocks for optical packet switching.
Various techniques have been suggested by the prior art to provide random access memory at high speeds, but have not been successfully implemented. For instance deflection routing, a technique suggested to reduce the probability of blocking, has been analyzed on regular meshed networks such as Manhattan Street (MS) and Shuffle Network (SN) networks, which are suitable for local area networks (LAN) and metropolitan area networks (MAN). The deflection routing technique avoids collisions between packets by deflecting (mis-routing) one of the packets in conflict with another packet in a different direction. If buffers are not available, any mis-routed packets can be temporarily deflected to an undesired link. Thus, deflection routing allows the use of fiber links as optical buffers while maintaining bit-rate transparency.
Queuing management is another technique that has been suggested to reduce the probability of blocking of packets by managing in an intelligent way the injection of packets into the network. If an injection is possible but the packet to be injected is in conflict and the router cannot solve the conflict, the next packet in the queue, with no conflict with the flow-through packets, is selected for injection.
Another technique suggested for conflict reduction is wavelength dimensioning. This technique consists of creating a wavelength over-capacity on the network. For example, this can be achieved if the network uses 16 wavelengths per link and instead of using all of the 16 wavelengths to inject packets, a reduced number of wavelengths are employed. This technique basically reduces the traffic load per wavelength and, therefore, the probability of packet loss at every node. The optical IP routers should be capable of handling both short and long packets efficiently as the IP traffic is bimodal in nature: short packets which are typical of transactional-style flows and large packets, or bursts, that are encountered in the transport of large data blocks.
Accordingly, it is desirable to implement an optical routing system and method using FDL optical buffers to reduce or eliminate dropping of variable length data packets due to blocking conflicts.
Accordingly, the present invention is directed to a dynamic optical routing system and method employing fiber delay line (FDL) optical buffering for wavelength dimension multiplexing (WDM) of variable length data packets.
Wavelength conversion is a technique utilized in the present invention to reduce the probability of blocking in both circuit-switching and packet-switching wavelength routed optical networks. This technique solves blocking by converting the packets in conflict to other available wavelengths, thereby solving the conflict. As the number of wavelengths used to route the data packets increase, the probability of packet loss decreases.
Optical buffering employs fiber delay lines (FDLs)of different lengths equivalent to a multiple of a data packet duration. The data packet duration corresponds to the number of bits chosen to make up a data packet. The size of the optical buffer, and thus the number of fiber delay lines, is one of the most critical design parameters.
Accordingly, one aspect of the present invention can be characterized as providing a round robin method for routing of data packets. In this aspect of the present invention when new packets arrive at the optical router, they usually come from different ports. In a WDM network, each port is considered as one wavelength. The newly arriving packets can be labeled as a wavelength and a fiber number of the FDL. For instance if the port is number 3 and the fiber is fiber number 2 of the FDL optical buffer, the packet will be denoted as (3,2), which is read as wavelength number three of the input fiber two. If the processing of the new incoming packets is performed in an ascending order based on the fiber and wavelength, it is denoted as xe2x80x9csequence orderingxe2x80x9d of the new variable length data packets.
If it is assumed there are (n) wavelengths in one set of FDLs for each output fiber, when new packets are scheduled to arrive at time to the order of the wavelength assignment will be n=xcex1xcex2, . . . , xcexn, xcex1, xcex2, . . . , xcexn, . . . . In the present invention this ordering is called xe2x80x9cround robin wavelength assignmentxe2x80x9d.
For example, if it is assumed that there are only three available wavelengths (i.e. n=xcex1, xcex2xcex3) and there are seven data packets to be routed, the ordering of the wavelengths will be as follows: For packet 1, n=xcex1; packet 2, n=xcex2, packet 3, n=xcex3; packet 4 n=xcex1; packet 5 n=xcex2, packet 6 n=xcex3; packet 7, n=xcex1. In the above example the last wavelength (n) assigned was (n)=xcex1. For the next batch of conflicted data packets, the algorithm starts the assigning of wavelength process at (n)=xcex2 and the next wavelength would be n=xcex3 and so on. In an alternative embodiment, the wavelength assignment could be set to revert to (n)=xcex1 for each new batch of conflicted data packets or the wavelength could be set to some alternate predetermined wavelength.
In a xe2x80x9cPure round robin wavelength assignmentxe2x80x9d a method is used wherein, upon the arrival of new packets at the router, the packets are picked in sequence order. Each packet is assigned to a wavelength as per the round robin wavelength assignment procedure. The packet will be assigned to a wavelength without knowing the occupancy status of the FDL optical buffer. If the wavelength of the assigned fiber is full, then the packet will be dropped. This procedure will be repeated until all the newly arrived packets are processed.
Another aspect of the present invention can be characterized as providing a round robin method with memory for routing of data packets. In this method, upon the arrival of new packets at the router, a controller will select the packets in sequence or some predetermined order or randomly. A wavelength is selected for each packet in the FDL buffer according to the round robin rule. Each assignment of wavelength is stored in a memory and the occupancy of the wavelength is noted. If this wavelength is full, that is, the total number of time slots in this wavelength has been used to handle other data packets, the wavelength is marked as full and no additional packets will be assigned to it. This procedure is repeated for each wavelength. If all wavelengths are fully occupied, then the remaining packets will be dropped. This procedure guarantees the full utilization of the FDL optical buffer.
In an alternate embodiment the wavelength (n) can be selected in predetermined order. For instance, the assignment process could first exhaust the even wavelengths (n) and then the odd wavelengths until all wavelength (n) in the FDL are exhausted. Realistically any predetermined ordering is applicable as long as each wavelength (n) is utilized before a wavelength is used a second, third, or nth time.
In an alternate embodiment, the wavelength may be polled later to review its status in case its FDL buffer has cleared some of the wavelengths and if so the wavelengths are placed back in service. The polling may be triggered by a predetermined time or a predetermined number of drops criteria. This aspect would most likely be employed in very high traffic scenarios wherein a large number of packets are arriving at the router simultaneously, but after the initial surge the number or arrivals slows.
A further aspect of the present invention can be characterized as providing a round robin with memory and determining a minimally occupied FDL fiber wavelength for routing of data packets. This modification of the round robin with memory method employs additionally the finding of the minimally occupied wavelength of the FDL optical buffer. Newly arriving packets are picked in sequence order, as in the round robin with memory method, and before assigning a wavelength to the new packet, the minimum occupancy wavelength of the FDL optical buffer is determined. The packet is then assigned to this wavelength. If the shortest occupancy buffer is full, then by default, all buffers are full and, therefore, all remaining packets are dropped. For each new packet, this procedure is repeated until the newly arrived data packets are exhausted or a determination is made to drop all remaining packets.
In an alternate embodiment, after a predetermined period of time or predetermined number of dropped data packets the algorithm resumes determining the minimally occupied wavelength as some of the FDL wavelengths may have cleared and now have capacity to receive new data packets. This is especially the case wherein the FDL optical buffer has a default wavelength of long duration wherein data packets are dumped for an extended period to decrease the probability that the data packets will be dropped. The assignment process continues until all data packets are assigned or until the command is sent to drop all packets.
A still further aspect of the present invention can be characterized as providing a xe2x80x9cshortest packet first then assign to minimum occupancy bufferxe2x80x9d method. In this method incoming packets are sorted in ascending order based on the data packet size, wherein the shortest length data packet is processed first. Each packet will be assigned to the least occupied wavelength as described above. The memory will be updated to reflect the new assignment and the next new arriving data packet will be processed in the sorted order and assigned to the updated least occupied wavelength.
Additional aspects and advantages of the invention will be set forth in part in the description which follows, and in part will be obvious from the description, or may be learned by practice of the invention. The aspects and advantages of the invention will be realized and attained by means o the elements and combinations particularly pointed out in the appended claims.
To achieve these and other advantages, and in accordance with the purpose of the present invention, as embodied and broadly described, the present invention can be characterized according to one aspect as a method for wavelength division multiplexing (WDM) fiber delay line (FDL) optical buffer routing and scheduling of conflicted variable length data packets through an optical router. This method includes the steps of ordering of each conflicted variable length data packet and selecting each of the data packets in turn for routing based on the ordering sequence. The method then sequentially assigns each conflicted data packet a wavelength in the FDL optical buffer from (n) available wavelengths, wherein (n)=xcex1, xcex2, . . . , xcexn, xcex1, xcex2, . . . , xcexn, . . . Each data packet is then converted to the sequentially assigned wavelength (n) and the data packets are routed to an optical buffer according to the wavelength assignment. The method further determines if the wavelength of the FDL optical buffer is fully occupied and if so the data packet is dropped.
The present invention can be characterized according to another aspect of the present invention as system for wavelength division multiplexing (WDM) fiber delay line (FDL) optical buffer routing and scheduling of conflicted variable length data packets through an optical router employing a memory. The system includes a fiber delay line optical buffer, an optical router, wherein the optical router is capable performing the steps of: ordering each conflicted variable length data packet; selecting each of the data packets in turn for routing based on the ordering sequence; sequentially assigning each conflicted data packet a wavelength in the FDL optical buffer,from (n) available wavelengths, wherein n=xcex1, xcex2, . . . , xcexn, xcex1, xcex2, . . . , xcexn, . . . ; converting each data packet to the sequentially, assigned wavelength (n); and routing the data packets to an optical buffer according to the wavelength assignment, wherein if the wavelength of the FDL optical buffer is fully occupied the data packet is dropped.
The present invention can be characterized according to a further aspect of the present invention as a method for wavelength division multiplexing (WDM) fiber delay line (FDL) optical buffer routing and scheduling of conflicted variable length data packets through an optical router. The method includes the means for ordering of each conflicted variable length data packet, means for selecting each of the data packets in turn for routing based on the ordering sequence, means for sequentially assigning each conflicted data packet a wavelength in the FDL optical buffer from (n) available wavelengths, wherein (n)=xcex1, xcex2, . . . , xcexn, xcex1, xcex2, . . . , xcexn, . . . Means for converting each data packet to the sequentially assigned wavelength (n) are employed as well as means for routing the data packets to an optical buffer according to the wavelength assignment, and determining if the wavelength of the FDL optical buffer is fully occupied and if so the data packet is dropped.
The present invention can be also characterized according to a still further aspect of the present invention as a method for wavelength division multiplexing (WDM) fiber delay line (FDL) optical buffer routing and scheduling of conflicted variable length data packets through an optical router employing a memory. The method includes the steps of ordering of each conflicted variable length data packet and selecting each of the data packets in turn for routing based on the ordering sequence and then sequentially assigning each conflicted data packet a wavelength in the FDL optical buffer from (n) available wavelengths, wherein n=xcex1, xcex2, . . . , xcexmn, xcex1, xcex2, . . . , xcexn, . . . The wavelengths of the FDL optical buffer that each data packet was assigned to is stored in memory and the occupancy status of each wavelength in the FDL optical buffer is also stored in memory. Each data packet is converted to the sequentially assigned wavelength (n) and the data packets are routed to the FDL optical buffer according to the wavelength assignment, wherein a determining if the stored occupancy status of the assigned wavelength of the FDL optical buffer is fully occupied and if so that wavelength is marked as full and no further data packets will be assigned to that wavelength and the assignment of wavelengths will continue sequentially eliminating any wavelength marked as full and a data packet will only be dropped after all wavelengths are marked as full.
The present invention can be characterized according to another aspect of the present invention as a method for wavelength division multiplexing (WDM) fiber delay line (FDL) optical buffer routing and scheduling of conflicted data packets through an optical router with memory, the method including the steps of ordering of each conflicted data packet:
(a) means for selecting in ordered sequence each of the data packets for routing;
(b) means for selecting a next wavelength (n) in sequence to be assigned from (n) available wavelengths of said FDL optical buffer, wherein the sequencing of (n) is (n)=xcex1, xcex2, . . . , xcexn, xcex1, xcex2, . . . , xcexn, . . . ;
(c) means for determining if a buffer capacity of the wavelength (n) selected, wherein if the data packet length is less than or equal to the buffer capacity of the wavelength (n) selected the data packet is assigned to the wavelength, and wherein if the data packet length is greater than the buffer capacity, recording the wavelength (n) in memory and steps (b) and (c) are repeated until all wavelengths (n) have been exhausted and recorded or a suitable wavelength is located, if no wavelength has sufficient capacity the data packet is dropped and the next data packet is selected;
means for converting each data packet to the assigned wavelength (n); and
means for routing the data packets to an optical buffer according to the wavelength assignment, and repeating steps (b) and (c) until all conflicted data packets are exhausted.
The present invention can be characterized according to a still further aspect of the present invention as a method for wavelength division multiplexing (WDM) fiber delay line (FDL) optical buffer routing of conflicted variable length data packets through an optical router having a memory, to minimize wavelength occupancy, the method including the steps of:
ordering of each conflicted variable length data packet;
(a) selecting each of the data packets in turn for routing based on the ordering sequence;
(b) determining occupancy status of each wavelength in a FDL optical buffer and storing occupancy status to a memory;
(c) determining a minimally occupied wavelength (n) of the FDL optical buffer;
(d) converting the wavelength of the selected data packet to the wavelength of the minimally occupied wavelength and routing the selected data packet to the minimally occupied wavelength;
(e) updating the occupancy status of each wavelength in the FDL optical buffer and storing to memory;
(f) selecting the next data packet and repeating steps (c) through (e) for each data packet, wherein if it is determined that the minimally occupied wavelength cannot accept the data packet, the data packet and all subsequent data packets are dropped.
The present invention can be characterized according to another aspect of the present invention as a method for wavelength division multiplexing (WDM) fiber delay line (FDL) optical buffer routing of conflicted variable length data packets through an optical router including a memory to a minimum occupancy wavelength. The method includes the steps of; ordering of each conflicted variable length data packet; (a) selecting each of the data packets in turn for routing based on the ordering sequence; (b) determining occupancy status of each wavelength in a FDL optical buffer and storing occupancy status to a memory; (c) determining a minimally occupied wavelength of the FDL optical buffer; (d) converting the wavelength of the selected data packet to the wavelength of the minimally occupied wavelength and routing the selected data packet to the minimally occupied wavelength; (e) updating the occupancy status of each wavelength in the FDL optical buffer and storing to memory; (f) selecting the next data packet and repeating steps (c) through (e) for each data packet, and if it is determined that the minimally occupied wavelength cannot accept the data packet, the data packet and all subsequent data packets are dropped.
The present invention can be characterized according to another aspect of the present invention as a method for wavelength division multiplexing (WDM) fiber delay line (FDL) optical buffer routing of conflicted variable length data packets through an optical router including a memory to a minimum occupancy wavelength. The method including the steps of ordering of each conflicted variable length data packet by shortest length data packet to longest length data packet; (a) selecting each of the data packets in turn for routing based on the ordering sequence; (b) determining occupancy status of each wavelength in a FDL optical buffer and storing occupancy status to a memory; (c) determining a minimally occupied wavelength of the FDL optical buffer; (d) converting the wavelength of the selected data packet to the wavelength of the minimally occupied wavelength and routing the selected data packet to the minimally occupied wavelength; (e) updating the occupancy status of each wavelength in FDL optical buffer and storing to memory; (f) selecting the next data packet and repeating steps (c) through (e) for each data packet, and if it is determined that the minimally occupied wavelength cannot accept the data packet, the data packet and all subsequent data packets are dropped.
It is to be understood that both the foregoing general description and the following detailed description are exemplary and explanatory only and are not restrictive of the invention, as claimed.